1. Related Application
The subject matter of this application is related to the subject matter in a co-pending non-provisional application by inventors Nicolai Kosche, Milton E. Barber, Peter C. Damron, Douglas Walls and Sidney J. Hummert filed on Apr. 15, 2000 entitled, “Disambiguating Memory References Based Upon User-Specified Programming Constraints,” having Ser. No. 09/549,806. This related application is hereby incorporated by reference in order to support the instant application.
2. Field of the Invention
The present invention relates to the process of developing and debugging software for computer systems. More specifically, the present invention relates to a method and an apparatus for detecting violations of type rules in a computer program.
3. Related Art
Compilers perform many optimizations during the process of translating computer programs from human-readable source code form into machine-readable executable code form. Some of these optimizations improve the performance of a computer program by reorganizing instructions within the computer program so that the instructions execute more efficiently. For example, it is often advantageous to initiate a read operation in advance of where the data returned by the read operation is used in the program so that other instructions can be executed while the read operation is taking place.
Unfortunately, the problem of “aliasing” greatly restricts the freedom of a compiler to reorganize instructions to improve the performance of a computer program. The problem of aliasing arises when two memory references can potentially access the same location in memory. If this is the case, one of the memory references must be completed before the other memory reference takes place in order to ensure that the program executes correctly. For example, an instruction that writes a new value into a memory location cannot be moved so that it occurs before a preceding instruction that reads from the memory location without changing the value that is read from the memory location.
The problem of aliasing is particularly acute for programs that make extensive use of memory references through pointers, because pointers can be easily modified during program execution to point to other memory locations. Hence, an optimizer must typically assume that a pointer can reference any memory location. This assumption greatly limits the performance improvements that can the achieved by a code optimizer.
One solution to this problem is to use a strongly typed computer programming language, such as Pascal, that restricts the way in which pointers can be manipulated. For example, in a strongly typed language, a pointer to a floating point number cannot be modified to point to an integer. Hence, an optimizer is able to assume that pointers to floating pointer numbers cannot be modified to point to integers, and vice versa. The drawback of using strongly typed languages is that strong type restrictions can greatly reduce the freedom of the programmer.
An alternative solution is to construct a code optimizer that detects all of the aliasing conditions that can arise during program execution. Unfortunately, the task of detecting all of the aliasing conditions that can potentially arise is computationally intractable and/or undecidable for all but the most trivial computer programs.
Another solution is to use programming standards. The C programming language standard imposes type-based restrictions on the way pointers may be used in standard-conforming programs. Unfortunately, these programming standards are flagrantly ignored in programs of enormous economic importance, such as major database applications. Consequently, compilers do not use the restrictions imposed by programming standards to achieve better performance.
The process of determining whether two memory references alias is known as alias “disambiguation.” Note that alias disambiguation is typically performed through inter-procedural pointer analysis, which is intractable in both space and time for large commercial applications.
What is needed is a method and an apparatus that makes validation of type-based restrictions tractable for large commercial applications.